package com.lw.leetcode.arr.b;

/**
 * 713. 乘积小于K的子数组
 * 剑指 Offer II 009. 乘积小于 K 的子数组
 *
 * @Author liw
 * @Date 2021/6/25 17:03
 * @Version 1.0
 */
public class NumSubarrayProductLessThanK {

    public static void main(String[] args) {
        NumSubarrayProductLessThanK test = new NumSubarrayProductLessThanK();

        // [10,5,2,6], k = 100 8
        int[] arr = {14};
        int k = 13;
        int i = test.numSubarrayProductLessThanK(arr, k);
        System.out.println(i);
    }

    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k == 0) {
            return 0;
        }
        int sum = 0;
        int count = 0;
        int value = 1;
        int length = nums.length;
        int st = 0;
        for (int i = 0; i < length; i++) {
            int num = nums[i];
            value *= num;
            count++;
            if (value < k) {
                sum += count;
            } else {
                while (value >= k) {
                    value /= nums[st++];
                    count--;
                    if (st > i) {
                        break;
                    }
                }
                if (st <= i) {
                    sum += count;
                }

            }
        }
        return sum;
    }

}
